package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 左叶子之和
 * @date 2025/4/16 17:15
 */
public class SumOfLeftLeaves_404 {

    /**
     * dmsxl：dfs-迭代
     * <p>
     * 思路：同递归，node的左孩子存在且为叶子节点才记录节点值
     */
    public int sumOfLeftLeaves4(TreeNode root) {
        if (root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        int result = 0;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null && node.left.left == null && node.left.right == null) {
                result += node.left.val;
            }
            if (node.right != null) stack.add(node.right);
            if (node.left != null) stack.add(node.left);
        }
        return result;
    }

    /**
     * dmsxl：dfs-递归-后序
     * <p>
     * 思路：父节点去收集左叶子的节点值
     * <p>
     * 分析：
     * 1.空节点和叶子节点都结束本层递归，向上返回0；因为，虽然是叶子节点，但并不知道它是左叶子还是右，需要回到该节点上层递归，结合其父节点判断。
     * 2.左右中遍历顺序，左孩子递归完后，若它还是叶子节点，才记录节点值。
     */
    public int sumOfLeftLeaves3(TreeNode root) {
        return dfs3(root);
    }

    public int dfs3(TreeNode node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return 0;

        // 左
        int leftSum = dfs3(node.left);
        TreeNode leftNode = node.left;
        // 左孩子非空，且为叶子节点，则记录左叶子节点值
        if ((leftNode != null && leftNode.left == null && leftNode.right == null)) {
            leftSum += leftNode.val;
        }

        // 右
        // 右孩子的 左叶子节点值也要记录
        int rightSum = dfs3(node.right);

        // 中
        return leftSum + rightSum;
    }

    /**
     * 个解：dfs-迭代
     * <p>
     * 分析：
     * 1.左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点。
     * 2.判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
     */
    public int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        // root不入队，是因为例题只有根节点root看作它没有左叶子。
        // 所以，直接入队root的左右孩子
        queue.offer(root.left);
        queue.offer(root.right);
        int sum = 0;
        while (!queue.isEmpty()) {
            // 一次出队两个节点，保证first为左节点
            TreeNode first = queue.poll();
            TreeNode second = queue.poll();

            // 左、右都空
            if (first == null && second == null) continue;

            // 左不空
            if (first != null) {
                // 记录左叶子的节点值
                if (first.left == null && first.right == null) {
                    sum += first.val;
                }
                queue.offer(first.left);
                queue.offer(first.right);
            }
            // 右不空
            if (second != null) {
                queue.offer(second.left);
                queue.offer(second.right);
            }

        }

        return sum;
    }

    /**
     * 个解：dfs-递归-后序
     * <p>
     * 分析；确认这里sum是否为隐藏回溯？——本题不涉及回溯，只需要统计左叶子节点的节点值。
     */
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, 0, false);
    }

    public int dfs(TreeNode node, int sum, boolean leftFlag) {
        if (node == null) return 0;
        // 右叶子节点，返回0
        if (node.left == null && node.right == null && !leftFlag) return 0;

        // 左叶子节点，返回节点值
        if (node.left == null && node.right == null) return node.val;

        // 左
        int left = dfs(node.left, sum, true);
        // 右
        int right = dfs(node.right, sum, false);

        // 中
        return sum + left + right;
    }

}
